{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Restore IP Addresses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: restoreIpAddresses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #复原 IP 地址"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>有效 IP 地址</strong> 正好由四个整数（每个整数位于 <code>0</code> 到 <code>255</code> 之间组成，且不能含有前导 <code>0</code>），整数之间用 <code>'.'</code> 分隔。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如：<code>\"0.1.2.201\"</code> 和<code> \"192.168.1.1\"</code> 是 <strong>有效</strong> IP 地址，但是 <code>\"0.011.255.245\"</code>、<code>\"192.168.1.312\"</code> 和 <code>\"192.168@1.1\"</code> 是 <strong>无效</strong> IP 地址。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个只包含数字的字符串 <code>s</code> ，用以表示一个 IP 地址，返回所有可能的<strong>有效 IP 地址</strong>，这些地址可以通过在 <code>s</code> 中插入&nbsp;<code>'.'</code> 来形成。你 <strong>不能</strong>&nbsp;重新排序或删除 <code>s</code> 中的任何数字。你可以按 <strong>任何</strong> 顺序返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"25525511135\"\n",
    "<strong>输出：</strong>[\"255.255.11.135\",\"255.255.111.35\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0000\"\n",
    "<strong>输出：</strong>[\"0.0.0.0\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"101023\"\n",
    "<strong>输出：</strong>[\"1.0.10.23\",\"1.0.102.3\",\"10.1.0.23\",\"10.10.2.3\",\"101.0.2.3\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 20</code></li>\n",
    "\t<li><code>s</code> 仅由数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [restore-ip-addresses](https://leetcode.cn/problems/restore-ip-addresses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [restore-ip-addresses](https://leetcode.cn/problems/restore-ip-addresses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"25525511135\"', '\"0000\"', '\"101023\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        if not s:\n",
    "            return res\n",
    "        \n",
    "        def getValidIP(st, path):\n",
    "            if st and len(path) <= 3:\n",
    "                if len(path) == 3:\n",
    "                    if st == '0' or (int(st) <= 255 and not st.startswith('0')):\n",
    "                        res.append(path + [st])\n",
    "                else:\n",
    "                    getValidIP(st[1:], path+[st[0]])\n",
    "                    if not st.startswith('0'):\n",
    "                        getValidIP(st[2:], path+[st[:2]])\n",
    "                        if int(st[:3])<=255:\n",
    "                            getValidIP(st[3:], path+[st[:3]])\n",
    "                                   \n",
    "        getValidIP(s, [])\n",
    "        return ['.'.join(e) for e in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        self.dfs(s, [], res)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, s, result, res):\n",
    "        if len(s) > (4 - len(result)) * 3:\n",
    "            return\n",
    "        if not s and len(result) == 4:\n",
    "            res.append('.'.join(result))\n",
    "            return\n",
    "        for i in range(min(3, len(s))):\n",
    "            curr = s[:i+1]\n",
    "            if (curr[0] == '0' and len(curr) >= 2) or int(curr) > 255:\n",
    "                break\n",
    "            self.dfs(s[i+1:], result + [curr], res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if len(s) <= 0:\n",
    "            return []\n",
    "        # s = s[::-1]\n",
    "        result_list = []\n",
    "        for i in range(1, 4):\n",
    "            count = 0\n",
    "            temp_list = []\n",
    "            temp_string = s[:i]\n",
    "            if int(temp_string) > 255 or str(int(temp_string)) != temp_string:\n",
    "                continue\n",
    "            temp_list.append(temp_string)\n",
    "            self.dfs(s[i:], temp_list, result_list, count + 1)\n",
    "        return list(set(result_list))\n",
    "\n",
    "    def dfs(self, s, temp, result, count):\n",
    "        if s == \"\" and count == 4:\n",
    "            result.append(\".\".join(temp))\n",
    "            return\n",
    "        if (s != \"\" and count == 4) or s == \"\":\n",
    "            return\n",
    "        for i in range(1, 4):\n",
    "            temp_string = s[:i]\n",
    "            temp_list = copy.deepcopy(temp)\n",
    "            if int(temp_string) > 255 or str(int(temp_string)) != temp_string:\n",
    "                continue\n",
    "            # result.insert(0, temp_string)\n",
    "            temp_list.append(temp_string)\n",
    "            self.dfs(s[i:], temp_list, result, count + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if len(s) < 4:\n",
    "            return []\n",
    "        route = {}\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i, len(s)):\n",
    "                tmp = s[i:j+1]\n",
    "                if len(tmp) > 1 and tmp[0] == '0':\n",
    "                    continue\n",
    "                if int(tmp) <= 255:\n",
    "                    if i in route:\n",
    "                        route[i].append(j)\n",
    "                    else:\n",
    "                        route[i] = [j]\n",
    "        ans = []\n",
    "        self.dfs(s, '', ans, 0, route, 0)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "    def dfs(self, s, cur, ans, count, route, start):\n",
    "        if count == 4 and start == len(s):\n",
    "            ans.append(cur)\n",
    "            return\n",
    "        if start == len(s) or count == 4:\n",
    "            return\n",
    "        for i in route[start]:\n",
    "            if count == 3:\n",
    "                self.dfs(s, cur+s[start:i+1], ans, count+1, route, i+1)\n",
    "            else:\n",
    "                self.dfs(s, cur+s[start:i+1]+'.', ans, count+1, route, i+1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return []\n",
    "        ret = []\n",
    "        self.helper(s, 0, [], ret)\n",
    "        return ret\n",
    "\n",
    "    def helper(self, s, pos, temp, result):\n",
    "        limit = 4\n",
    "        if len(temp) == limit and pos == len(s):\n",
    "            result.append(\".\".join(list(temp)))\n",
    "            return\n",
    "        if len(temp) >= limit:\n",
    "            return\n",
    "        i = pos\n",
    "        x = 0\n",
    "        while i + x < (len(s) + 1) and x <= 3:\n",
    "            t = s[i:i + x]\n",
    "            if self.isValid(t) and len(temp) < 4:\n",
    "                temp.append(t)\n",
    "                self.helper(s, pos + x, temp, result)\n",
    "                temp.pop()\n",
    "            x += 1\n",
    "\n",
    "    def isValid(self, s):\n",
    "        if len(s) >= 1 and len(s) <= 3:\n",
    "            if len(s) > 1 and s[0] == '0':\n",
    "                return False\n",
    "            n = int(s)\n",
    "            return n >= 0 and n <= 255\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if len(s) > 12:\n",
    "            return []\n",
    "        res = []\n",
    "        self.dfs(s, [], res)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, s, path, res):\n",
    "        if not s and len(path) == 4:\n",
    "            res.append('.'.join(path))\n",
    "            return res\n",
    "        for i in range(1, 4):\n",
    "            if i > len(s):\n",
    "                continue\n",
    "            number = int(s[:i])\n",
    "            if str(number) == s[:i] and number <= 255: #对于001,01情况\n",
    "                self.dfs(s[i:], path + [s[:i]], res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        \n",
    "        ans = []\n",
    "        \n",
    "        n = len(s)\n",
    "        for i1 in range(1, 4):\n",
    "            if i1 >= n or i1 + 2 >= n:\n",
    "                continue\n",
    "            if int(s[:i1]) > 255:\n",
    "                continue\n",
    "            if s[:i1] != '0' and s[0] == '0':\n",
    "                continue\n",
    "                \n",
    "            for i2 in range(i1 + 1, i1 + 4):\n",
    "                if i2 >= n or i2 + 1 >= n:\n",
    "                    continue\n",
    "                if int(s[i1:i2]) > 255:\n",
    "                    continue\n",
    "                if s[i1:i2] != '0' and s[i1] == '0':\n",
    "                    continue\n",
    "                \n",
    "                for i3 in range(i2 + 1, n):\n",
    "                    if int(s[i2:i3]) > 255 or int(s[i3:]) > 255 or (n - i3) > 3:\n",
    "                        continue\n",
    "                    \n",
    "                    if s[i2:i3] != '0' and s[i2] == '0':\n",
    "                        continue\n",
    "                    if s[i3:] != '0' and s[i3] == '0':\n",
    "                        continue\n",
    "                    \n",
    "                    ans.append('{}.{}.{}.{}'.format(s[:i1], s[i1:i2], s[i2:i3], s[i3:]))\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        l = len(s)\n",
    "        if l >= 13 or l < 4:\n",
    "            return []\n",
    "\n",
    "        ret = []\n",
    "        for i1 in range(3):\n",
    "            if i1 > l-4 or int(s[0:i1+1]) > 255:\n",
    "                break\n",
    "            if s[0] == '0' and i1 > 0:\n",
    "                break\n",
    "            for i2 in range(i1+1, i1+4):\n",
    "                if i2 > l-3 or int(s[i1 + 1:i2 + 1]) > 255:\n",
    "                    break\n",
    "                if s[i1+1] == '0' and i2 > i1+1:\n",
    "                    break\n",
    "                for i3 in range(i2+1, i2+4):\n",
    "                    if i3 > l-2 or int(s[i2+1:i3+1]) > 255:\n",
    "                        break\n",
    "                    if s[i2+1] == '0' and i3 > i2+1:\n",
    "                        break\n",
    "\n",
    "                    if s[i3+1] == '0' and l-1 > i3+1:\n",
    "                        continue\n",
    "                    if l - 1 - i3 <= 3 and int(s[i3+1:]) <= 255:\n",
    "\n",
    "                        ret.append('.'.join([s[0:i1 + 1], s[i1 + 1:i2 + 1], s[i2 + 1:i3 + 1], s[i3 + 1:]]))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        ans = []\n",
    "        for i in range(1, 4):\n",
    "            for j in range(i + 1, i + 4):\n",
    "                for k in range(j + 1, j + 4):\n",
    "                    if k >= len(s):\n",
    "                        continue\n",
    "                    if len(s) - k>3:\n",
    "                        continue\n",
    "                    if (s[j]=='0' and k!=j+1) or (s[k]=='0' and len(s)!=k+1) or (s[i]=='0' and j!=i+1) or (s[0]=='0' and i!=1):\n",
    "                        continue\n",
    "                    x1 = int(s[:i])\n",
    "                    x2 = int(s[i:j])\n",
    "                    x3 = int(s[j:k])\n",
    "                    x4 = int(s[k:])\n",
    "                    if x1 < 256 and x2 < 256 and x3 < 256 and x4 < 256:\n",
    "                        ans.append('{}.{}.{}.{}'.format(str(x1), str(x2), str(x3), str(x4)))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = []\n",
    "    def run(self, done, todo, cnt):\n",
    "        if len(todo) < cnt:\n",
    "            return\n",
    "        if len(todo) > 3 * cnt:\n",
    "            return\n",
    "        if cnt == 1:\n",
    "            if len(todo) > 1 and todo[0] == '0':\n",
    "                return\n",
    "            if int(todo) < 256:\n",
    "                self.res.append(done + todo)\n",
    "            return\n",
    "        for i in range(1, min(4, len(todo))):\n",
    "            if i > 1 and todo[0] == '0':\n",
    "                break\n",
    "            if i == 3 and int(todo[0:3]) > 255:\n",
    "                break\n",
    "            self.run(done + todo[0:i] + '.', todo[i:], cnt - 1)\n",
    "        \n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        self.run('', s, 4)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        self.ans = []\n",
    "        self.helper(s,0,0,\"\")\n",
    "        return self.ans\n",
    "\n",
    "    def helper(self,s,count,idx,sub_str):\n",
    "        if count > 4:\n",
    "            return\n",
    "        n = len(s)\n",
    "        if count == 4 and idx == n:\n",
    "            self.ans.append(sub_str)\n",
    "            return\n",
    "\n",
    "        for i in range(1,4):\n",
    "            if idx+i>n:\n",
    "                break\n",
    "            temp = s[idx:idx + i]\n",
    "            if (len(temp)>1 and temp[0] == \"0\") or (int(temp)>255):\n",
    "                continue\n",
    "            if count != 3:\n",
    "                temp += \".\"\n",
    "            self.helper(s,count+1,idx+i,sub_str+temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def _f(self, s, index, cnt, path, res):\n",
    "        if index >= len(s):\n",
    "            if cnt == 4:\n",
    "                if path[1:] not in res:\n",
    "                    res.append(path[1:])\n",
    "            else:\n",
    "                return\n",
    "        else:\n",
    "            self._f(s, index+1, cnt+1, path + '.' + s[index:index+1], res)\n",
    "            if int(s[index:index+2]) >= 10:\n",
    "                self._f(s, index+2, cnt+1, path + '.' + s[index:index+2], res)\n",
    "            if int(s[index:index+3]) <= 255 and int(s[index:index+3]) >= 100:\n",
    "                self._f(s, index+3, cnt+1, path + '.' + s[index:index+3], res)\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if len(s) > 12:\n",
    "            return res\n",
    "        self._f(s, 0, 0, '', res)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        self.n = len(s)\n",
    "        self.tmp = []\n",
    "        self.res = []\n",
    "        self.s = s\n",
    "        self.dfs(0,0)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self,start,count):\n",
    "        if start>=self.n:\n",
    "            if count==self.n and len(self.tmp)==4:\n",
    "                strs = \".\".join(self.tmp.copy())\n",
    "                self.res.append(strs)\n",
    "            return\n",
    "        for i in range(3):\n",
    "            strs = self.s[start:i+1+start]\n",
    "            if self.is_true(strs): \n",
    "                self.tmp.append(strs)\n",
    "                #进行剪支\n",
    "                if len(self.tmp)>4:\n",
    "                    self.tmp.pop()\n",
    "                    return\n",
    "                self.dfs(i+start+1,i+1+count)\n",
    "                self.tmp.pop()\n",
    "    def is_true(self,nums):\n",
    "        #验证无效字符串 \"011\"\n",
    "        if nums[0]==\"0\" and len(nums)!=1:\n",
    "            return False\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res = res*10+int(nums[i])\n",
    "        if res>=0 and res<=255:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        self.n = len(s)\n",
    "        self.tmp = []\n",
    "        self.res = []\n",
    "        self.s = s\n",
    "        self.dfs(0,0)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self,start,count):\n",
    "        if start>=self.n:\n",
    "            if count==self.n and len(self.tmp)==4:\n",
    "                strs = \".\".join(self.tmp.copy())\n",
    "                self.res.append(strs)\n",
    "            return\n",
    "        for i in range(3):\n",
    "            strs = self.s[start:i+1+start]\n",
    "            if self.is_true(strs): \n",
    "                self.tmp.append(strs)\n",
    "                #进行剪支\n",
    "                if len(self.tmp)>4:\n",
    "                    self.tmp.pop()\n",
    "                    return\n",
    "                self.dfs(i+start+1,i+1+count)\n",
    "                self.tmp.pop()\n",
    "    def is_true(self,nums):\n",
    "        #验证无效字符串 \"011\"\n",
    "        if nums[0]==\"0\" and len(nums)!=1:\n",
    "            return False\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            res = res*10+int(nums[i])\n",
    "        if res>=0 and res<=255:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        res = []\n",
    "        self.generator(res, s, \"\", 0, 0)\n",
    "        return res\n",
    "\n",
    "    def generator(self, res, s, temp, start, count):\n",
    "        if count == 4:\n",
    "            if start == len(s):\n",
    "                res.append(temp)\n",
    "            return\n",
    "\n",
    "        for i in range(1, 4):\n",
    "            if start + i > len(s):\n",
    "                break\n",
    "\n",
    "            subIp = s[start: start + i]\n",
    "            if (len(subIp) > 1 and subIp[0] == \"0\") or (i == 3 and int(subIp) >= 256):\n",
    "                break;\n",
    "            self.generator(res, s, temp + subIp + (\".\" if count < 3 else \"\"), start + i, count + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        self.dfs(s, 0, \"\", res)\n",
    "        return res\n",
    "        \n",
    "    def dfs(self, s, dot_cnt, path, res):\n",
    "        if dot_cnt == 4:\n",
    "            if not s:\n",
    "                res.append(path[:-1])\n",
    "            return\n",
    "        for i in range(1, 4):\n",
    "            if i <= len(s):\n",
    "                if i == 1:\n",
    "                    self.dfs(s[i:], dot_cnt + 1, path + s[:i] + '.', res)\n",
    "                elif i == 2 and s[0] != '0':\n",
    "                    self.dfs(s[i:], dot_cnt + 1, path + s[:i] + '.', res)\n",
    "                elif i == 3 and s[0] != '0' and int(s[:3]) <= 255:\n",
    "                    self.dfs(s[i:], dot_cnt + 1, path + s[:i] + '.', res)\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        res = []\n",
    "        self.dfs(s, 0, \"\", res)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, s, index, path, res):\n",
    "        if index == 4:\n",
    "            if not s:\n",
    "                res.append(path[:-1])\n",
    "            return # backtracking\n",
    "        for i in range(1, 4):\n",
    "            if i <= len(s):\n",
    "                if int(s[:i]) <= 255:\n",
    "                    self.dfs(s[i:], index+1, path+s[:i]+\".\", res)\n",
    "                if s[0] == \"0\":  # here should be careful \n",
    "                    break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        res = []\n",
    "        self.generator(res, s, \"\", 0, 0)\n",
    "        return res\n",
    "\n",
    "    def generator(self, res, s, temp, start, count):\n",
    "        if count == 4:\n",
    "            if start == len(s):\n",
    "                res.append(temp)\n",
    "            return\n",
    "\n",
    "        for i in range(1, 4):\n",
    "            if start + i > len(s):\n",
    "                break\n",
    "\n",
    "            subIp = s[start: start + i]\n",
    "            if (len(subIp) > 1 and subIp[0] == \"0\") or (i == 3 and int(subIp) >= 256):\n",
    "                break;\n",
    "            self.generator(res, s, temp + subIp + (\".\" if count < 3 else \"\"), start + i, count + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: 'str') -> 'List[str]':\n",
    "        res=[]\n",
    "        self.dfs(s,[],res)\n",
    "        return res\n",
    "    \n",
    "    def dfs(self,s,path,res):\n",
    "        if len(s)>(4-len(path))*3:\n",
    "            return\n",
    "        if not s and len(path)==4:\n",
    "            res.append('.'.join(path))\n",
    "            return\n",
    "        for i in range(min(3,len(s))):\n",
    "            curr = s[:i+1]\n",
    "            if (curr[0] == '0' and len(curr)>=2) or int(curr) > 255:\n",
    "                   continue\n",
    "            self.dfs(s[i+1:], path + [s[:i+1]], res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if not s: return []\n",
    "        \n",
    "        if len(s) < 4 or len(s) > 12: return []\n",
    "        res = []\n",
    "        \n",
    "        def isvalid(ip):\n",
    "            if ip[0] == '0': return ip == '0'\n",
    "            return 0<int(ip)<=255\n",
    "        def dfs(s, temp, res, count):\n",
    "            if count == 3 and isvalid(s):\n",
    "                res.append(temp + s)\n",
    "                return\n",
    "            for i in range(1, min(4, len(s))):\n",
    "                if isvalid(s[:i]):\n",
    "                    dfs(s[i:], temp+s[:i] + '.', res, count+1)\n",
    "        dfs(s, \"\", res, 0)\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        S = [([], s)]\n",
    "        while S:\n",
    "            l, s = S.pop()\n",
    "            if len(l) == 4:\n",
    "                if not s:\n",
    "                    res.append('.'.join(l))\n",
    "            elif len(s) <= (4 - len(l)) * 3:\n",
    "                for i in range(min(3, len(s) - 3 + len(l))):\n",
    "                    if i != 2 or s[:3] <= '255':\n",
    "                        S.append((l + [s[:i+1]], s[i+1:]))\n",
    "                    if s[0] == '0':\n",
    "                        break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        l = len(s)\n",
    "        if l < 4 or l > 12:\n",
    "            return []\n",
    "        ll = list(s)\n",
    "        res = []\n",
    "        for a in range(1, 4):\n",
    "            if a > 1 and s[0] == '0':\n",
    "                continue\n",
    "            if a == 3 and s[0:a] > '255':\n",
    "                continue\n",
    "            for b in range(1, 4):\n",
    "                if a + b >= l:\n",
    "                    continue\n",
    "                if b > 1 and s[a] == '0':\n",
    "                    continue\n",
    "                if b == 3 and s[a:a+b] > '255':\n",
    "                    continue\n",
    "                for c in range(1, 4):\n",
    "                    if c > 1 and s[a+b] == '0':\n",
    "                        continue\n",
    "                    if c == 3 and s[a+b:a+b+c] > '255':\n",
    "                        continue\n",
    "                    d = l - a - b - c\n",
    "                    if d <= 0 or d >= 4:\n",
    "                        continue\n",
    "                    if d == 3 and s[a+b+c:] > '255':\n",
    "                        continue\n",
    "                    if d > 1 and s[a+b+c] == '0':\n",
    "                        continue\n",
    "                    res.append('.'.join([s[0:a], s[a:a+b], s[a+b:a+b+c], s[a+b+c:]]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s):\n",
    "        res = []\n",
    "        self.dfs(s, 0, \"\", res)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def dfs(self, s, index, path, res):\n",
    "        if index == 4:\n",
    "            if not s:\n",
    "                res.append(path[:-1])\n",
    "            return  # backtracking\n",
    "        for i in range(1, 4):\n",
    "            # the digits we choose should no more than the length of s\n",
    "            if i <= len(s):\n",
    "                #choose one digit\n",
    "                if i == 1:\n",
    "                    self.dfs(s[i:], index+1, path+s[:i]+\".\", res)\n",
    "                #choose two digits, the first one should not be \"0\"\n",
    "                elif i == 2 and s[0] != \"0\":\n",
    "                    self.dfs(s[i:], index+1, path+s[:i]+\".\", res)\n",
    "                #choose three digits, the first one should not be \"0\", and should less than 256\n",
    "                elif i == 3 and s[0] != \"0\" and int(s[:3]) <= 255:\n",
    "                    self.dfs(s[i:], index+1, path+s[:i]+\".\", res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "\n",
    "        def dfs(i,j,temp):\n",
    "            print(i,j,temp)\n",
    "            if i==4 and j==n-1:\n",
    "                res.append('.'.join(temp))\n",
    "            for l in range(j+1,min((j+4),n)):\n",
    "                if (n-l-1)>(4-i-1)*3:\n",
    "                    continue\n",
    "                if int(s[j+1:l+1])>255 or (l>j+1 and s[j+1]=='0'):\n",
    "                    continue\n",
    "                temp.append(s[j+1:l+1])\n",
    "                dfs(i+1,l,temp)\n",
    "                temp.pop()\n",
    "        \n",
    "        dfs(0,-1,[])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if s == '' or len(s) > 12:\n",
    "            return []\n",
    "        res = []\n",
    "\n",
    "        def dfs(start, ipsegs, ipadress, s):\n",
    "            if start > len(s):\n",
    "                return\n",
    "            if start == len(s)  and ipsegs == 4:\n",
    "                res.append(ipadress)\n",
    "                return\n",
    "            if start + 0 < len(s):\n",
    "                dfs(start + 1, ipsegs + 1, ipadress + '.' + s[start], s)\n",
    "                if s[start] != '0':\n",
    "                    if start + 1 < len(s):\n",
    "                        dfs(start + 2, ipsegs + 1, ipadress + '.' + s[start:start + 2], s)\n",
    "                    if start+2 < len(s) and int(s[start:start + 3]) <= 255:\n",
    "                        dfs(start + 3, ipsegs + 1, ipadress + '.' + s[start:start + 3], s)\n",
    "\n",
    "        dfs(0 + 1, 0 + 1, s[0], s)\n",
    "        if s[0] != '0':\n",
    "            dfs(0 + 2, 0 + 1, s[0:0 + 2], s)\n",
    "            if int(s[0:0 + 3]) <= 255:\n",
    "                dfs(0 + 3, 0 + 1, s[0:0 + 3], s)\n",
    "\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = \"\"\n",
    "        result = []\n",
    "        if len(s) < 4:\n",
    "            return []\n",
    "        for i in range(min(3,len(s)-3)):\n",
    "            if str(int(s[:i+1])) == s[:i+1] and int(s[:i+1]) <= 255:\n",
    "                for j in range(min(3,len(s[i+1:])-2)):\n",
    "                    if str(int(s[i+1:i+j+2])) == s[i+1:i+j+2] and int(s[i+1:i+j+2]) <= 255:\n",
    "                        for k in range(min(3,len(s[i+j+2:])-1)):\n",
    "                            if str(int(s[i+j+2:i+j+k+3])) == s[i+j+2:i+j+k+3] and int(s[i+j+2:i+j+k+3]) <= 255:\n",
    "                                if str(int(s[i+j+k+3:])) == s[i+j+k+3:] and int(s[i+j+k+3:]) <= 255:\n",
    "                                    res += s[:i+1] + \".\" + s[i+1:i+j+2] + \".\" + s[i+j+2:i+j+k+3] + \".\" + s[i+j+k+3:]\n",
    "                                    result.append(res)\n",
    "                                    res = \"\"\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        out = []\n",
    "        if not s or len(s) > 12 or len(s) < 4:\n",
    "            return out\n",
    "        \n",
    "        num = len(s)\n",
    "        part = num // 4\n",
    "        def backtrack(s, tmp):\n",
    "            if len(tmp) == 4:\n",
    "                if not s:\n",
    "                    res = \"\".join(str(num) + \".\" for num in tmp)\n",
    "                    out.append(res.rstrip('.'))\n",
    "                \n",
    "                return\n",
    "            \n",
    "            for idx in range(1, 4):\n",
    "                if not s or len(s) < idx:\n",
    "                    return\n",
    "                if int(s[:idx]) > 255:\n",
    "                    continue\n",
    "                if idx > 1 and s[0] == '0':\n",
    "                    return\n",
    "                \n",
    "                backtrack(s[idx:], tmp + [int(s[:idx])])\n",
    "\n",
    "        backtrack(s, [])\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        num=4\n",
    "        H=[0]*4\n",
    "        length=len(s)\n",
    "        ans=[]\n",
    "        def digui(start,number):\n",
    "            if number==num:\n",
    "                if start==length:\n",
    "                    p='.'.join(H)\n",
    "                    ans.append(p)\n",
    "                return\n",
    "            if start==length:\n",
    "                return\n",
    "            if s[start]==\"0\":\n",
    "                H[number]='0'\n",
    "                digui(start+1,number+1)\n",
    "            res=0\n",
    "            for i in range(start,length):\n",
    "                res=10*res+int(s[i])\n",
    "                if 0<res<=0xff:\n",
    "                   \n",
    "                    H[number]=str(res)\n",
    "                    print(i+1,number+1)\n",
    "                    digui(i+1,number+1)\n",
    "                else:\n",
    "                    break\n",
    "        digui(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        if len(s) < 4 or int(s) < 0 or int(s) > 255255255255:\n",
    "            return []\n",
    "        @lru_cache()\n",
    "        def backTracing(s):\n",
    "            if s.count('.') == 3:\n",
    "                tempNum = s.split('.')[-1]\n",
    "                if tempNum != '':\n",
    "                    if str(int(tempNum)) == tempNum and 0<= int(tempNum) <= 255:\n",
    "                        res.append(s)\n",
    "            tempNum = s.split('.')[-1]\n",
    "            pre = '' if tempNum == s else s[:-len(tempNum)]\n",
    "            for i in range(len(tempNum)):\n",
    "                if str(int(tempNum[:i+1])) == tempNum[:i+1]:\n",
    "                    if 0<= int(tempNum[:i+1]) <= 255:\n",
    "                        newS = pre + tempNum[:i+1] + '.' + tempNum[i+1:]\n",
    "                        backTracing(newS)\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        res = []\n",
    "        backTracing(s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as dd\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def backtrack(i, cnt):\n",
    "            if cnt == 3:\n",
    "                if s[i:] in book:\n",
    "                    memo[(i, cnt)].add(s[i:])\n",
    "                return memo[(i, cnt)]\n",
    "            if (i, cnt) in memo:\n",
    "                return memo[(i, cnt)]\n",
    "            for j in range(3):\n",
    "                if i+j == len(s):\n",
    "                    break\n",
    "                if s[i:i+j+1] in book:\n",
    "                    for part in backtrack(i+j+1, cnt+1):\n",
    "                        memo[(i, cnt)].add(s[i:i+j+1]+'.'+part)\n",
    "            return memo[(i, cnt)]\n",
    "        memo = dd(set)\n",
    "        book = set([str(x) for x in range(256)])\n",
    "        return list(backtrack(0, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ## 切割字符串：1. 只能切成四部分 2. 数字范围在0-255, 0不能开头\n",
    "        res = []\n",
    "        path = []\n",
    "        def backtrack(s, path, startindex):\n",
    "            ## 中止条件\n",
    "            if len(path) >= 4:\n",
    "                if startindex >= len(s):\n",
    "                    res.extend([path[0]+'.'+path[1]+'.'+path[2]+'.'+path[3]])\n",
    "                return\n",
    "            \n",
    "            for i in range(startindex, len(s)):\n",
    "                temp = s[startindex: i+1]\n",
    "                if int(temp) > 255:  ## 剪枝：如果大于255，直接break中止该轮递归\n",
    "                    break\n",
    "                ## 核心条件\n",
    "                if len(str(int(temp))) == len(temp):\n",
    "                    path.append(temp)\n",
    "                    backtrack(s, path, i+1)\n",
    "                    path.pop()\n",
    "                else:\n",
    "                    continue\n",
    "        backtrack(s, path, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, s: str, remainDot: int) -> list:\n",
    "        if s == '':\n",
    "            return []\n",
    "        if remainDot == 0:\n",
    "            if int(s) >= 0 and int(s) < 256:\n",
    "                return [str(int(s))]\n",
    "            return []\n",
    "        res = []\n",
    "        for i in range(max(len(s),3)):\n",
    "            ts = s[:i + 1]\n",
    "            if int(ts) < 256:\n",
    "                for j in self.dfs(s[i + 1:], remainDot - 1):\n",
    "                    res.append(str(int(ts)) + '.' + j)\n",
    "        return res\n",
    "\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res=[]\n",
    "        for i in self.dfs(s,3):\n",
    "            if len(i)== len(s)+3:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        self.result.clear()\n",
    "        if len(s) > 12: return []\n",
    "        self.backreavseering(s,0,0)\n",
    "        return self.result\n",
    "    \n",
    "    def backreavseering(self,s,start_index,point_num):\n",
    "        if point_num == 3:\n",
    "            if self.is_valid(s,start_index,len(s)-1):\n",
    "                self.result.append(s[:])\n",
    "            return self.result\n",
    "        \n",
    "        for i in range(start_index,len(s)):\n",
    "            if self.is_valid(s,start_index,i):\n",
    "                s = s[:i+1] + '.' + s[i+1:]\n",
    "                self.backreavseering(s,i+2,point_num+1)\n",
    "                s = s[:i+1] + s[i+2:]\n",
    "            else:\n",
    "                break\n",
    "    def is_valid(self,s,start,end):\n",
    "        if start > end: return False\n",
    "        if s[start] == '0' and start != end:\n",
    "            return False\n",
    "        if not 0 <= int(s[start:end+1]) <= 255:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\r\n",
    "        SEG_COUNT = 4\r\n",
    "        ans = []\r\n",
    "        segments = [0] * SEG_COUNT\r\n",
    "\r\n",
    "        def dfs(segId: int, segStart: int):\r\n",
    "            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案\r\n",
    "            if segId == SEG_COUNT:\r\n",
    "                if segStart == len(s):\r\n",
    "                    ipAddr = '.'.join(str(seg) for seg in segments)\r\n",
    "                    ans.append(ipAddr)\r\n",
    "                return\r\n",
    "            \r\n",
    "            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯\r\n",
    "            if segStart == len(s):\r\n",
    "                return\r\n",
    "\r\n",
    "            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0\r\n",
    "            if s[segStart] == \"0\":\r\n",
    "                segments[segId] = 0\r\n",
    "                dfs(segId + 1, segStart + 1)\r\n",
    "            \r\n",
    "            # 一般情况，枚举每一种可能性并递归\r\n",
    "            addr = 0\r\n",
    "            for segEnd in range(segStart, len(s)):\r\n",
    "                addr = addr * 10 + ord(s[segEnd]) - ord('0')\r\n",
    "                if 0 < addr <= 255:\r\n",
    "                    segments[segId] = addr\r\n",
    "                    dfs(segId + 1, segEnd + 1)\r\n",
    "                else:\r\n",
    "                    break\r\n",
    "\r\n",
    "        dfs(0, 0)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\r\n",
    "        SEG_COUNT = 4\r\n",
    "        ans = []\r\n",
    "        segments = [0] * SEG_COUNT\r\n",
    "\r\n",
    "        def dfs(segId: int, segStart: int):\r\n",
    "            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案\r\n",
    "            if segId == SEG_COUNT:\r\n",
    "                if segStart == len(s):\r\n",
    "                    ipAddr = \".\".join(str(seg) for seg in segments)\r\n",
    "                    ans.append(ipAddr)\r\n",
    "                return\r\n",
    "            \r\n",
    "            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯\r\n",
    "            if segStart == len(s):\r\n",
    "                return\r\n",
    "\r\n",
    "            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0\r\n",
    "            if s[segStart] == \"0\":\r\n",
    "                segments[segId] = 0\r\n",
    "                dfs(segId + 1, segStart + 1)\r\n",
    "            \r\n",
    "            # 一般情况，枚举每一种可能性并递归\r\n",
    "            addr = 0\r\n",
    "            for segEnd in range(segStart, len(s)):\r\n",
    "                addr = addr * 10 + ord(s[segEnd]) - ord('0')\r\n",
    "                if 0 < addr <= 255:\r\n",
    "                    segments[segId] = addr\r\n",
    "                    dfs(segId + 1, segEnd + 1)\r\n",
    "                else:\r\n",
    "                    break\r\n",
    "\r\n",
    "        dfs(0, 0)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        '''\n",
    "        本质切割问题使用回溯搜索法，本题只能切割三次，所以纵向递归总共四层\n",
    "        因为不能重复分割，所以需要start_index来记录下一层递归分割的起始位置\n",
    "        添加变量point_num来记录逗号的数量[0,3]\n",
    "        '''\n",
    "        self.result.clear()\n",
    "        if len(s) > 12: return []\n",
    "        self.backtracking(s, 0, 0)\n",
    "        return self.result\n",
    "\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "    \n",
    "    def backtracking(self, s: str, start_index: int, point_num: int) -> None:\n",
    "        # Base Case\n",
    "        if point_num == 3:\n",
    "            if self.is_valid(s, start_index, len(s)-1):\n",
    "                self.result.append(s[:])\n",
    "            return\n",
    "        # 单层递归逻辑\n",
    "        for i in range(start_index, len(s)):\n",
    "            # [start_index, i]就是被截取的子串\n",
    "            print(start_index,i)\n",
    "            if self.is_valid(s, start_index, i):\n",
    "                s = s[:i+1] + '.' + s[i+1:]\n",
    "                self.backtracking(s, i+2, point_num+1)  # 在填入.后，下一子串起始后移2位\n",
    "                s = s[:i+1] + s[i+2:]    # 回溯\n",
    "            else:\n",
    "                # 若当前被截取的子串大于255或者大于三位数，直接结束本层循环\n",
    "                break\n",
    "    def is_valid(self, s: str, start: int, end: int) -> bool:\n",
    "        if start > end: return False\n",
    "        # 若数字是0开头，不合法\n",
    "        if s[start] == '0' and start != end:\n",
    "            return False\n",
    "        if not 0 <= int(s[start:end+1]) <= 255:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "#         result=[]\n",
    "#         path=[]\n",
    "\n",
    "# # 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法\n",
    "#         def isValid(s,start,end):\n",
    "#             # print(\"s[startIndex:i]\",s[start:end+1])\n",
    "#             if (start > end) :\n",
    "#                 return False;\n",
    "#             print(\"start\",start)\n",
    "#             # if start==end:\n",
    "#             #     return False\n",
    "#             if s[start] == '0' and start != end: # 0开头的数字不合法\n",
    "#                     return False;\n",
    "#             num = 0;\n",
    "#             for i in range(start,end+1):\n",
    "#             # for (int i = start; i <= end; i++):\n",
    "#                 if (s[i] > '9' or s[i] < '0'): # 遇到非数字字符不合法\n",
    "#                     return False;\n",
    "#                 num = num * 10 + (ord(s[i]) - ord('0'));\n",
    "#                 if (num > 255): # 如果大于255了不合法\n",
    "#                     return False;\n",
    "#             return True;\n",
    "\n",
    "           \n",
    "#         def backTracking(s:str,startIndex:int,pointNum:int):\n",
    "#             # pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。\n",
    "#             if pointNum==3:\n",
    "#                 # 判断第四段子字符串是否合法，如果合法就放进result中\n",
    "#                 if isValid(s, startIndex, len(s) - 1):\n",
    "#                     result.append(s);\n",
    "#                 return;\n",
    "            \n",
    "#             for i in range(startIndex,len(s)):\n",
    "#                 print(startIndex,i)\n",
    "#                 print(\"s[startIndex:i+1]\",s[startIndex:i+1])\n",
    "#                 # print(type(s[startIndex:i+1]))\n",
    "#                 print(\"isValid(s,startIndex,i)\",isValid(s,startIndex,i))\n",
    "#                 # 判断合法性\n",
    "#                 if isValid(s,startIndex,i): #判断 [startIndex,i] 这个区间的子串是否合法\n",
    "#                     str_list = list(s)\n",
    "#                     str_list.insert(i+1,'.')\n",
    "#                     s = ''.join(str_list)   #在i的后面插入一个逗点\n",
    "#                     # print(s)\n",
    "#                     pointNum+=1\n",
    "#                     backTracking(s,i+2,pointNum)  #插入逗点之后下一个子串的起始位置为i+2\n",
    "#                     str_list=list(s)              #回溯删掉逗点\n",
    "#                     del str_list[i+1]\n",
    "#                     s = ''.join(str_list)\n",
    "#                     pointNum-=1\n",
    "#                 else:\n",
    "#                     continue\n",
    "\n",
    "#         backTracking(s,0,0)\n",
    "#         return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def back_tracking(idx, seg_nums):\n",
    "            if idx == len(s) and seg_nums == 4:\n",
    "                res.append('.'.join(path[:]))\n",
    "                return\n",
    "            if idx > len(s) or seg_nums > 4:\n",
    "                return\n",
    "\n",
    "            # i 表示 从哪个位置截止, 左闭右开\n",
    "            for i in range(idx+1, len(s)+1):\n",
    "                # 什么情况下可以从idx位置截止呢\n",
    "                # 1. 字符最短为1 ， 字符为 3\n",
    "                # 2. 当字符长为1 时可以以 0开始， 不为1时不能以0开始\n",
    "                # 3. 0~255 之间\n",
    "                if (i - idx) >= 1 and (i-idx) <= 3:\n",
    "                    if (i-idx) > 1 and s[idx] == '0':\n",
    "                        continue\n",
    "                    if int(s[idx:i]) >= 256:\n",
    "                        continue\n",
    "                    path.append(s[idx:i])\n",
    "                    back_tracking(i, seg_nums+1)\n",
    "                    path.pop()\n",
    "\n",
    "        back_tracking(0, 0)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        result = []\n",
    "        ip_addr = \"\"\n",
    "        point_num = 0\n",
    "        self.backtracking(s, 0, result, ip_addr, point_num)\n",
    "        return result\n",
    "    \n",
    "    def backtracking(self, s, start_index, result, ip_addr, point_num):\n",
    "        if point_num == 3:\n",
    "            if self.is_valid(s, start_index, len(s) - 1):\n",
    "                ip_addr += s[start_index:]\n",
    "                result.append(ip_addr)\n",
    "            return\n",
    "        \n",
    "        for i in range(start_index, len(s)):\n",
    "            if not self.is_valid(s, start_index, i):\n",
    "                break\n",
    "            \n",
    "            sub = s[start_index: i + 1]\n",
    "            point_num += 1\n",
    "            self.backtracking(s, i + 1, result, ip_addr + sub + \".\", point_num)\n",
    "            point_num -= 1\n",
    "    \n",
    "    def is_valid(self, s, start_index, end):\n",
    "        if start_index > end:\n",
    "            return False\n",
    "        if s[start_index] == \"0\" and start_index != end:\n",
    "            return False\n",
    "        return 0 <= int(s[start_index: end + 1]) <= 255"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        if not s: return ans\n",
    "\n",
    "        def dfs(cur_i, tmp):\n",
    "            nonlocal ans\n",
    "            if cur_i == len(s) and len(tmp) == 4:\n",
    "                ans.append(\".\".join(tmp[:]))\n",
    "                return\n",
    "            if len(tmp) > 3:\n",
    "                return\n",
    "            num = \"\"\n",
    "            for i in range(cur_i, min(cur_i+3, len(s))):\n",
    "                num += s[i]\n",
    "                if int(num) > 255:\n",
    "                    return\n",
    "                if len(num) > 1 and num[0] == '0':\n",
    "                    return\n",
    "                dfs(i+1, tmp+[num])\n",
    "\n",
    "        dfs(0, [])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
